import java.util.LinkedList;
import java.util.List;

public class Solution115 {
    public int numDistinct(String s, String t) {
        int result=0;
        if(s.equals(t)){
            return 1;
        }
        else if(t.length()==1){
            for (int i = 0; i < s.length(); i++) {
                if(s.charAt(i)==t.charAt(0)){
                    result++;
                }
            }
            return result;
        }
        List<Integer>[] DP=new List[s.length()];
        for (int i = 0; i < s.length(); i++) {
            DP[i]=new LinkedList<>();
            char tmpC=s.charAt(i);
            if(tmpC==t.charAt(0)){
                DP[i].add(0);
            }
            for (int j = 0; j < i; j++) {
                for (int tmp:DP[j]) {
                    int ind=tmp+1;
                    if(t.charAt(ind)==tmpC){
                        if(ind==(t.length()-1)){
                            result++;
                        }
                        else {
                            DP[i].add(ind);
                        }
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution115 s=new Solution115();
        System.out.println(s.numDistinct("rabbbit",
                "rabbit"));
    }
}
